package com.数据结构.堆;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.UUID;

public class HeapSort {

    public static void main(String[] args) {
        int [] arr = {5,100,9,77,8,7,2};
        int[] randomArr = new int[7];
        Random random = new Random();
        List nums = new ArrayList();
        for(int i = 0;i<7;i++){
            int num = random.nextInt(30 + 1);
            while(nums.contains(num)){
                num = random.nextInt(30 + 1);
            }
            nums.add(num);
            randomArr[i] = num;
        }

        sort(randomArr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(randomArr[i]+ " ");
        }
    }

    public static void sort(int[] pq){
        int n = pq.length;
        for (int i = n/2-1;i>=0;i--){
            siftDown(pq,i,n);
        }
        for (int i = n-1; i >0 ; i--) {
            swap(pq,i,0);
            siftDown(pq,0,i);
        }

    }
    public static void siftDown(int[] pq,int k,int n){
        while(2*k+1<n){
            int i = k;
            if(2*k+2<n && pq[2*k+1]<pq[2*k+2]){
                k=2*k+2;
            }else{
                k=2*k+1;
            }
            if(pq[k]>pq[i] ){
                swap(pq,k,i);
            }else{
                break;
            }
        }
    }

//    public static void sort(int[] pq) {
//        int n = pq.length;
//        for (int i = n/2-1; i >=0; i--) {
//            siftDown(pq,i,n);
//        }
//        for (int i = n-1; i > 0 ; i--) {
//            swap(pq,i,0);
//            siftDown(pq,0,i);
//        }
//
//
//    }
//    private static void siftDown(int[] pq, int k, int n){
//        while (2*k+1<n){
//            int i = k;
//            if(2*k+2<n && pq[2*k+1]<pq[2*k+2]){
//                k=2*k+2;
//            }else{
//                k= 2*k+1;
//            }
//            if(pq[k]>pq[i]){
//                swap(pq,  k, i );
//            }else{
//                break;
//            }
//        }
//    }
    private static void swap(int[] pq,int a,int b){
        int tem = pq[a];
        pq[a] = pq[b];
        pq[b] = tem;
    }
}
